import java.util.*;

/**
 * @author 陈浩天
 * @version 1.0
 * @date 2021/9/2 14:00
 */
public class TestWorks {
    /**
     * 作业一：数据结构与算法基础
     * <p>
     * 判断数组中所有的数字是否只出现一次。给定一个数组array，判断数组 array 中是否所有的数字都只
     * 出现过一次。例如，arr = {1, 2, 3}，输出 YES。又如，arr = {1, 2, 1}，输出 NO。约束时间复杂度为 O(n)。
     */
    public static boolean checkNumRepeat(int[] array) {

        if (Objects.isNull(array)) {
            return true;
        }
        //创建新的容器,由于set 本身可以去重
        HashSet set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
            if (set.size() < i + 1) {
                //set 自动去重
                return false;
            }
        }
        return true;
    }

    /**
     * 作业二：数据结构与算法高级
     * <p>
     * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不
     * 同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人
     * 来挖掘……
     * 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半
     * 的金矿。要 求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
     * <p>
     * 思考:  已知----->   工人：  5个矿   ,共10名    200kg黄金/3人； 500kg黄金/5人；
     * int[] gold ={200,500,...,...,...}
     */

    /**
     * @param glodCount   矿数
     * @param peopleCount 人数
     * @param glod        数组g中存储每座金矿
     * @param people      数组p中存储挖每座金矿需要的工人数
     * @return 该方法返回工人数为w时挖数组g中前n座金矿所能得到的最大金矿数
     */

    public static int getMostGold(int glodCount, int peopleCount, int[] glod, int[] people) {
        if (glodCount > glod.length) {
            throw new RuntimeException("输入的n值大于给定的金矿数");
        }
        if (glodCount <= 1 && peopleCount < people[0]) {
            return 0;
        }
        // 挖完第一个矿
        if (glodCount == 1) {
            return glod[0];
        }
        //比较最后一个矿所挖需要的人数不够
        if (glodCount > 1 && peopleCount < people[glodCount - 1]) {
            return getMostGold(glodCount - 1, peopleCount, glod, people);
        }

        int a = getMostGold(glodCount - 1, peopleCount, glod, people);

        int b = getMostGold(glodCount - 1, peopleCount - people[glodCount - 1], glod, people) + glod[glodCount - 1];
        return Math.max(a, b);
    }
    public static void main(String[] args) {
        //1.题测

//        System.out.println(checkNumRepeat(new int[]{51,43,3,2,5}));

//        2.题测
        int[] glod = {400, 500, 200, 300, 350};
        int[] people = {4, 5, 3, 4, 3};
        System.out.println(getMostGold(5, 10, glod, people));
    }

}